package day_240507.e4;

public class e4_3 {
    public static void main(String[] args) {
        int n = 100;
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
       /* 这段代码是 Sieve of Eratosthenes 算法的核心部分，用于标记每个质数的倍数为非质数。

        1.外层循环：从2开始遍历到 n 的平方根，即 i * i <= n。这里之所以只遍历到平方根是因为对于一个数 n，
        如果它有大于平方根的质因子，那么它的另一个质因子一定小于平方根。因此只需遍历到平方根即可。

        2.内层循环：对于每个质数 i，如果 isPrime[i] 为 true，表示 i 是质数，则进入内层循环。

        3.内层循环从 i 的平方开始，即 j = i * i，因为小于 i 的倍数已经在之前的循环中被标记过了，
        所以从 i 的平方开始标记，以 i 为步长递增，即 j += i，将 i 的倍数都标记为 false，即非质数。

        这样做的目的是为了排除所有质数的倍数，因为一个数的倍数一定不是质数。通过这样的内层循环，可以一次性地排除所有质数的倍数，从而找出所有的质数。
*/
        int count = 0;
        System.out.print("质数：");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
                count++;
            }
        }
        System.out.println("\n质数共有：" + count);
    }
}
// 创建一个布尔数组 isPrime，长度为 n+1，用来标记每个数是否为质数。初始化时，将所有数都标记为 true，表示都是质数。

// 第一个循环从2开始遍历到 n，对于每个数 i，如果 isPrime[i] 为 true（即 i 是质数），则进入内部循环。

// 内部循环从 i 的平方开始，每次以 i 为步长递增，将 i 的倍数都标记为 false，因为它们不是质数。这样一轮循环结束后，所有 i 的倍数都被标记为非质数。

// 最后一个循环再次遍历数组，输出所有标记为 true 的数，即质数，并统计质数的个数。
